package cau.se.project;
import java.util.Arrays;
//import java.util.Scanner;
//import java.io.*;

public class Partitioning {
	
	private int[][] group = null;
	private int groupTill = 0;
	private int[][] info = null;
	private int emptyRowTill = 0;
	private int emptyColTill = 0;
	private int[][] array;
	
	public void setArray(int[][] getArray) {
		array = new int[getArray.length][getArray[0].length];
		for(int i=0; i<getArray.length; i++) {
			for(int j=0; j<getArray[0].length; j++) {
				array[i][j] = getArray[i][j];
			}
		}
		partition();
	}
	
	public int[][] getArray() {
		return array;
	}
	public int[][] getInfo() {
		return info;
	}
	public int[][] getGroup() {
		return group;
	}
	public int getlength() {
		return array.length;
	}
	private void partition() {
		try{ /*
			int[][] tempArray = {{0,0,0,0,0,0,0,0,0,0},
							     {1,0,0,0,0,0,0,0,0,0},
							     {0,0,0,0,1,0,0,1,0,0},
							     {0,0,0,0,0,0,0,0,0,0},
							     {0,0,1,0,0,0,0,1,0,0},
								 {0,0,0,0,0,0,0,0,0,0},
								 {0,0,0,0,0,0,0,0,0,1},
								 {0,0,0,0,1,0,0,0,0,0},
								 {1,0,0,0,0,0,0,0,0,0},
								 {0,0,0,1,0,0,0,0,0,0}}; 
			setArray(tempArray);
			*/
			
		group = new int[array.length][array.length];
		for(int i=0; i<group.length; i++) {
			for(int j=0; j<group.length; j++) {
				group[i][j] = -1;
			}
		}
		info = new int[array.length][2];
		for(int i=0; i<array.length; i++) {
			info[i][0] = i;
			info[i][1] = -1;
		}
		
		printArray(array);
		emptyColTill = array.length;
		emptyRowCheck(array);
		cycleCheck(array);
		
		printArray(array);
		printArray(group);

				}
		catch(Exception e){
			System.out.println("Error : ");
			e.printStackTrace();
		}
	}
	
	
	private void printArray(int array[][]) {
		for(int i=0; i<array.length; i++){
			for(int j=0; j<array[0].length; j++){
				System.out.print(array[i][j] + " ");
			}
			System.out.println();
		}
	}
	
	private void printArrayTemp(int array[]) {
		for(int i=0; i<array.length; i++){
				System.out.println(array[i]);
		}
	}
	
	private void changeRow(int array[][], int a, int b) {
		
		for(int i=0; i<array.length; i++) {
			int temp;
			temp = array[a][i];
			array[a][i] = array[b][i];
			array[b][i] = temp;
		}
		for(int j=0; j<array[0].length; j++) {
			int temp;
			temp = array[j][a];
			array[j][a] = array[j][b];
			array[j][b] = temp;
		}
		
		int temp1 = info[a][0];
		int temp2 = info[a][1];
		info[a][0] = info[b][0];
		info[a][1] = info[b][1];
		info[b][0] = temp1;
		info[b][1] = temp2;
	}
	
private void changeRow2(int array[][], int a, int b, int check) { // a���� b�� ����
		if(a<b){ // ���� ������ ����
			for(int c=a; c+1<=b; c++) {
				for(int i=0; i<array.length; i++) {
					int temp;
					temp = array[c][i];
					array[c][i] = array[c+1][i];
					array[c+1][i] = temp;
				}
				for(int j=0; j<array[0].length; j++) {
					int temp;
					temp = array[j][c];
					array[j][c] = array[j][c+1];
					array[j][c+1] = temp;
				}
				if(check == 0) {
					int temp1 = info[c][0];
					int temp2 = info[c][1];
					info[c][0] = info[c+1][0];
					info[c][1] = info[c+1][1];
					info[c+1][0] = temp1;
					info[c+1][1] = temp2;
				}
			}
		}
		else if(b<a){ // a����  ���� �ø�
			for(int c=a; c-1>=b; c--) {
				for(int i=0; i<array.length; i++) {
					int temp;
					temp = array[c][i];
					array[c][i] = array[c-1][i];
					array[c-1][i] = temp;
				}
				for(int j=0; j<array[0].length; j++) {
					int temp;
					temp = array[j][c];
					array[j][c] = array[j][c-1];
					array[j][c-1] = temp;
				}
				if(check == 0){
					int temp1 = info[c][0];
					int temp2 = info[c][1];
					info[c][0] = info[c-1][0];
					info[c][1] = info[c-1][1];
					info[c-1][0] = temp1;
					info[c-1][1] = temp2;
				}
			}
		}
	}

	private void changeValue(int a, int b) {
		int temp;
		temp = a;
		a = b;
		b = temp;
	}
	
	private void emptyRowCheck(int array[][]) {
		int PreValue = emptyRowTill;
		int m=0;
		for(int i=PreValue; i<array.length; i++){
			
			int emptyCheck = 0;
			for(int j=PreValue; j<array[0].length; j++){
				if(array[i][j] == 0) emptyCheck++;
			}
			if(emptyCheck == array[0].length-PreValue){

				changeRow(array, i, emptyRowTill);

				info[emptyRowTill][1] = groupTill;
				group[groupTill][m++] = info[emptyRowTill][0];

				emptyRowTill++;
			}
		}

		groupTill++;
		if(PreValue != emptyRowTill) {
			emptyRowCheck(array);
		}
		else if(PreValue == emptyRowTill) {
			groupTill--;
			emptyColCheck(array);
		}
	}
	
	private void emptyColCheck(int array[][]) {
		int PreValue = emptyRowTill;
		int PreValue2 = emptyColTill;
		int m=0;
		for(int j=emptyColTill-1; j>=PreValue; j--){
			int emptyCheck = 0;
			for(int i=PreValue; i<PreValue2; i++){
				if(array[i][j] == 0) emptyCheck++;
			}
			if(emptyCheck == array[j].length-PreValue-(array[0].length-PreValue2)){
				changeRow(array, j, emptyColTill-1);
						info[emptyColTill-1][1] = groupTill;
						group[groupTill][m++] = info[emptyColTill-1][0];
				emptyColTill--;
			}
		
		}
		groupTill++;
		if(PreValue2 != emptyColTill) emptyColCheck(array);
		else if(PreValue2 == emptyColTill) {
			groupTill--;
			
			
		}
	}
	private void emptyRowCheckInCycle(int array[][]) {
		int PreValue = emptyRowTill;
		for(int i=PreValue; i<array.length; i++){			
			int emptyCheck = 0;
			for(int j=emptyRowTill; j<emptyColTill; j++){
				if(array[i][j] == 0) emptyCheck++;
			}
			if((emptyCheck == emptyColTill-emptyRowTill) && (info[i][1] == -1)){
				changeRow(array, i, emptyRowTill);				
				emptyRowTill++;
			}
		}
		
		if(PreValue != emptyRowTill) {
			emptyRowCheckInCycle(array);
		}
	}
	
	private void cycleCheck(int array[][]) {
		boolean find = false;
		int[] cycleMatrix = null;
		int[] cycle = null;
		int i = emptyRowTill;
		cycleMatrix = new int[array.length];
		int cycleMatrixTill = 0; // cycle check �迭�� �Էµ� ���� ����
		
		for(int total = 0; (total <= emptyColTill-emptyRowTill) && !find && i < array.length; total++) {
			for(int j=emptyRowTill; j<emptyColTill && !find; j++) {
				if(array[i][j] == 1) {
					find = false; // cycle check �迭�� cycle�� ���� ���
					for(int c = 0; c < cycleMatrixTill; c++) {
						if(cycleMatrix[c] == j) { // true : c<= x < total ����Ŭ & boolean = true
							cycle = new int[cycleMatrixTill];
							for(int k=0; c+k < cycleMatrixTill; k++) {
								cycle[k] = cycleMatrix[c+k];
							}

							Arrays.sort(cycle);
							for(int n = 0; n < cycle.length; n++ ) {
 								changeRow(array, cycle[n], emptyRowTill);
								info[emptyRowTill][1] = groupTill;
								group[groupTill][n] = info[emptyRowTill][0];
								emptyRowTill++;
							}
							find = true;
							groupTill++;
						}
					}
					if(find == false) {
						cycleMatrix[cycleMatrixTill] = j;
						cycleMatrixTill++;
						i = j;
						j = emptyColTill;
					}
				}
				if(j+1 == emptyColTill) i++;
			}
		}
		int temp = emptyRowTill;		
		emptyRowCheckInCycle(array);
		emptyRowTill = temp;

		if(emptyColTill - emptyRowTill >= 1 && find == true) cycleCheck(array);
		else{
			System.gc(); 
			groupCycleCheck(array);
		}
	}
	
	private void groupCycleCheck(int[][] array) {

		int c=-1;
		int target=0;
		int[][] cca;
		cca = new int[array.length][array[0].length];

		for(int a=0; a<array.length; a++) {
			for(int b=0; b<array[0].length; b++) {
				cca[a][b] = array[a][b];
			}
		}
		for(int i=0; i<array.length; i++) {
			if(info[i][1] != c & info[i][1] != -1) {
				target = i;
				c = info[i][1];
			}
			else if(info[i][1] == c & info[i][1] != -1) {
				for(int j=0; j<array.length; j++) {
					cca[target][j] = (cca[target][j] | cca[i][j]);
					cca[j][target] = (cca[j][target] | cca[j][i]);
					cca[i][j] = 9;
					cca[j][i] = 9;
				}
			}
			
		}
	
		int m=0;
		boolean check = false;
		for(int i=0; i<array.length; i++) {
			for(int j=i+1; j<array[0].length; j++) {
				if((cca[i][j] & cca[j][i]) == 1) {
					int till=0;
					
					if(check == false) {
						if(info[i][1] != -1) {
							int ah = i;
							while(info[ah][1] == info[i][1]) {
								group[groupTill][m] = info[ah][0];
								m++;
								ah++;
							}
							till = ah;
						}
						else {
							info[i][1] = groupTill;
							group[groupTill][m] = info[i][0];
							m++;
	
						}
						
						if(info[j][1] != -1) {
							int ah = j;
							while(info[j][1] == info[j][1]) {
								group[groupTill][m] = info[ah][0];
								m++;
								ah++;
							}
						}
						else {
							info[j][1] = groupTill;
							group[groupTill][m] = info[j][0];
							m++;
						}
						
						check = true;
					}
					else {
						if(info[j][1] != -1) {
							int ah = j;
							while(info[ah][1] == info[j][1]) {
								group[groupTill][m] = info[ah][0];
								m++;
								ah++;
							}
						}
						else {
							info[j][1] = groupTill;
							group[groupTill][m] = info[j][0];
							m++;
						}
					}

					if(till != 0) {
						changeRow2(array, j, till, 0);
						groupTill++;
					}
				
					if(till != 0) changeRow2(cca, j, till, 1);
					for(int i1=0; i1<cca.length; i1++) {
						cca[till][i1] = 9;
						cca[i1][till] = 9;
					}
					
				}
			}
			if(check == true) groupTill++;
			check = false;
			m = 0;
			
		}
		for(int i=0; i<info.length; i++) {
			if(info[i][1] == -1) {
				
			}
		}
		int m1 = 0;
		for(int f=0; f<array.length; f++) {
			if(info[f][1] == -1) {
				info[f][1] = groupTill;
				group[groupTill][m1] = info[f][0];
				m1++;
			}
		}
		System.gc();
		

	}
}
